package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/subtree-of-another-tree/"> 另一棵树的子树(Subtree of Another Tree)</a>
 * <p>给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 * <p>
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。</p>
 * <pre>
 * 示例 1：
 *      输入：root = [3,4,5,1,2], subRoot = [4,1,2]
 *              root    3
 *                     / \
 *                    4   5     subtree     4
 *                   / \                   / \
 *                  1   2                 1   2
 *      输出：true
 *
 * 示例 2：
 * 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
 *              root    3
 *                     / \
 *                    4   5     subtree     4
 *                   / \                   / \
 *                  1   2                 1   2
 *                     /
 *                    0
 * 输出：false
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>root 树上的节点数量范围是 [1, 2000]</li>
 *     <li>subRoot 树上的节点数量范围是 [1, 1000]</li>
 *     <li>-104 <= root.val <= 104</li>
 *     <li>-104 <= subRoot.val <= 104</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/23 14:21
 */
public class LC0572IsSubtree_S {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //Queue<TreeNode> queue = new LinkedList<>();
        //queue.offer(root);
        return isSubtreeByRecursion(root, subRoot);
    }

    private boolean isSubtreeByRecursion(TreeNode node, TreeNode subRoot) {
        if (node == null) {
            return false;
        }
        return check(node, subRoot) || isSubtreeByRecursion(node.left, subRoot) || isSubtreeByRecursion(node.right, subRoot);
    }

    private boolean check(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null || root.val != subRoot.val) {
            return false;
        }
        return check(root.left, subRoot.left) && check(root.right, subRoot.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(4);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(0);
        TreeNode subtree = new TreeNode(4);
        subtree.left = new TreeNode(1);
        subtree.right = new TreeNode(2);
        LC0572IsSubtree_S lc0572IsSubtree_s = new LC0572IsSubtree_S();
        System.out.println(lc0572IsSubtree_s.isSubtree(root, subtree));
    }
}
